1. Field of the Invention
This invention relates to a division circuit and more particularly to a division circuit for signed division.
2. Description of the Prior Art
According to the prior art, when division on signed dividend and divisor expressed by a complement of 2 is carried out, in order to obtain an accurate quotient and remainder, if the dividend and/or divisor is negative, they are converted to positive values before the division. As a typical division algorithm, two examples of restoring type (pull-back method) and non-restoring type (pull-out method) will be described.
First, the conventional restoring type division algorithm will be explained referring to a structure of a division circuit shown in FIG. 1.
If a dividend of n bits is a and a divisor of m(n&gt;m) bits is b in FIG. 1, a division circuit comprises a remainder register 101 of n bits for storing high order side of a partial remainder during division operation and storing the remainder at the time of division end, a dividend/quotient register 102 of n bits for storing a dividend at the time of division start and successively storing low order side of the partial remainder and a quotient during division operation, a divisor register 103 of n bits for storing the divisor, a subtractor 104 of n bits, a selector 105 in which data obtained by combining a content of the remainder register 101 with that of a dividend/quotient register 102 is shifted by 1 bit so that the highest bit is shifted out, and then, data P# of that high order n bits, namely, data obtained by combining low order n-1 bits of the remainder register 101 with the highest bit of the dividend/quotient register 102 or output of the subtractor 104 is selected and supplied to the remainder register 101, and a control circuit 106 for determining a quotient by receiving division result of the subtractor 104 and selectively controlling the selector 105.
Next, the division operation using the division circuit having such a structure will be described according to its operation cycle.
First, if the dividend a and/or divisor b are negative, they/it are/is converted to positive numbers by taking complements thereof. If both are not negative, they are used as they are and these values are treated as a % and b % (first cycle, second cycle, action 1).
Next, the dividend a % is loaded on the dividend/quotient register 102 and then the divisor b % is loaded on the divisor register 103. 0 is loaded on all bits of the remainder register 101 (third cycle, action 2).
Then, the remainder register 101 and dividend register 102 are shifted by 1 bit to the left and high order n bit of data obtained by combining both the registers after the shift is assumed to be P# (fourth cycle, action 3-1). Then, the output data of the divisor register 103 is subtracted from data P# by means of the subtractor 104 (fourth cycle, action 3-2). Then, the content of the dividend/quotient register 102 is shifted by 1 bit to the left. When the output of the subtractor 104 is negative, 0 is written to the least significant bit of the dividend/quotient register 102 as a quotient. If the output of the subtractor 104 is not negative, 1 is written into the least significant bit of the dividend/quotient register 102 as a quotient (fourth cycle, action 3-3). Then, if the output of the subtractor 104 is not negative, the output of the subtractor 104 is stored in the remainder register 101, and when the output of the subtractor 104 is negative, data P# is stored in the remainder register 101 (pull-back method) (fourth cycle, action 3-4).
The actions (3-1)-(3-4) of aforementioned fourth cycle is repeated further (n-1) times (fifth cycle-(n+3) cycle).
Next, if the sign of the dividend is the same as the sign of the divisor, the output of the dividend/quotient register 102 is stored in the dividend/quotient register 102 as a quotient. On the other hand, if the sign of the dividend is different from the sign of the divisor, a complement of the output of the dividend/quotient register 102 is taken and written back to the dividend/quotient register 102 ((n+4) cycle, action 5).
Next, when the dividend is not negative, the output of the remainder register 101 is stored as a remainder. On the other hand, when the dividend is negative, a complement of the output of the remainder register 101 is taken and written to the remainder register 101 ((n+5) cycle, action 6).
Finally, the quotient is stored in the dividend/quotient register 102 and the remainder is stored in the remainder register 101, and then the signed division is terminated ((n+6) cycle, action 7).
The division processing is carried out as described above. FIG. 2 shows an example of division in which dividend a=1001(binary) (means-7 according to decimal notation) and divisor b=0011 (binary) (means 3 according to decimal notation). In FIG. 2, the content of the remainder register 101 is expressed by P, the content of the dividend/quotient register 102 is expressed by A and the content of the divisor register 103 is expressed by B.
Then, the conventional non-restoring type division algorithm will be described with reference to a structure of the division circuit shown in FIG. 3.
In the aforementioned conventional non-restoring type division, if the partial remainder is negative, a temporarily subtracted divisor is pulled back and added, so that the partial remainder is returned to a positive number. However, considering a level lower by a digit, subtraction of the divisor is regarded as (remainder+divisor).times.2-divisor. Then, because (remainder+divisor).times.2-divisor is remainder.times.2+divisor, when the partial remainder is negative, it is possible to store the partial remainder as it is and shift it by a bit to the left and then carry out addition instead of subtraction of the partial remainder and divisor. This method can reduce operation time per cycle as compared to the restoring type division. The non-restoring type division algorithm uses such a method.
If a dividend of n bits is a and a divisor of m(n&gt;m) bits is b in FIG. 3, a division circuit comprises a remainder register 111 of n bits for storing high order side of a partial remainder during division operation and storing the remainder at the time of division end, a dividend/quotient register 112 of n bits for storing a dividend at the time of division start and successively storing low order side of the partial remainder and a quotient during division operation, a divisor register 113 of n bits for storing the divisor, an adder/subtractor 114 of n bits, and a control circuit 115 for determining a quotient by receiving operation result of the adder/subtractor 114 and instructing the adder/subtractor 114 to carry out addition or subtraction according to operation result of the adder/subtractor 114.
Next, the division operation using the division circuit having such a structure will be described according to its operation cycle.
First, if the dividend a and/or divisor b are negative, they/it are/is converted to positive numbers by taking complements thereof. If both are not negative, they are used as they are and these values are treated as a % and b % (first cycle, second cycle, action 1).
Next, the dividend a % is loaded on the dividend/quotient register 112 and then the divisor b % is loaded on the divisor register 113. 0 is loaded on all bits of the remainder register 111 (third cycle, action 2).
Then, the remainder register 111 and dividend register 112 are shifted by 1 bit to the left and high order n bit of data obtained by combining both the registers after the shift is assumed to be P# (fourth cycle, action 3-1). Then, the output data of the divisor register 113 is subtracted from data P# by means of the subtractor 114 (fourth cycle, action 3-2). Then, the content of the dividend/quotient register 112 is shifted by 1 bit to the left. As for a value to be stored in the least significant bit of the dividend/quotient 112, when the output of the adder/subtractor 114 is negative, 0 is written into the least significant bit of the dividend/quotient register 112 as a quotient. If the output of the adder/subtractor 114 is not negative, 1 is written into the least significant bit of the dividend/quotient register 112 (fourth cycle, action 3-3). Subsequently, the output of the adder/subtractor 114 is stored in the remainder register 111 (fourth cycle, action 3-4).
In a next cycle, if the output of the remainder register 111 is negative, the remainder register 111 and dividend/quotient register 112 are shifted by a bit to the left. Then, data P# of high order n bits of data in which the contents of both the registers are combined after the shift and the output of the divisor register 113 are summed up by the adder/subtractor 114. On the other hand, if the output of the remainder register is not negative, the remainder register 111 and dividend/quotient register 112 are shifted by a bit to the left. Then, the output of the divisor register 113 is subtracted from data P# of high order n bits in which the contents of both the registers are combined after the shift by means of the adder/subtractor 114 (fifth cycle, action 4-1). Then, the content of the dividend/quotient register 112 is shifted by a bit to the left. When the output of the adder/subtractor 114 is negative, 0 is written into the least significant bit of the dividend/quotient register 112 as a quotient. If the output of the adder/subtractor is not negative, 1 is written therein as a quotient (fifth cycle, action 4-2). Then, the output of the adder/subtractor 114 is stored in the remainder register 111 (fifth cycle, action 4-3).
Next, the aforementioned action (4-1).about.(4-3) of the fifth cycle is repeated further (n-2) times (sixth cycle-(n+3) cycle).
If the output of the remainder register 111 is not negative, the remainder register 111 holds the value as it does. On the other hand, if the output of the remainder register 111 is negative, the output of the remainder register 111 and output of the divisor register 113 are summed up by means of the adder/subtractor 114 and its result is stored in the remainder register 111 ((n+4) cycle, action 6).
Next, if the sign of the dividend is the same as the sign of the divisor, the output of the dividend/quotient register 112 is stored in the dividend/quotient register 112. If the sign of the dividend is different from the sign of the divisor, a complement of the output of the dividend/quotient register 112 is taken and written back to the dividend/quotient register 112 ((n+5) cycle, action 7).
If the dividend is not negative, the output of the remainder register 111 is held. If the dividend is negative, a complement of the output of the remainder register 111 is taken and written back to the remainder register 111 ((n+6) cycle, action 8).
Finally, the quotient is stored in the dividend/quotient register 112 and the remainder is stored in the remainder register 111, and then the signed division is terminated ((n+7) cycle, action 9).
The division processing is carried out as described above. FIG. 4 shows an example of division in which dividend a=1001 (binary) (means-7 according to decimal notation) and divisor b=0011 (binary) (means 3 according to decimal notation) like the aforementioned conventional example. In FIG. 4, the content of the remainder register 111 is expressed by P, the content of the dividend/quotient register 112 is expressed by A and the content of the divisor register 113 is expressed by B.
As described above, when it is intended to obtain a quotient and remainder accurately in division operation of the signed dividend and divisor, if the dividend and/or divisor is negative, by taking a complement of 2, the negative values are converted to positive values and the division is carried out with positive dividend and divisor. Thus, if both the dividend and divisor are negative, a complement of 2 must be taken for both the values. Thus, a time for taking a complement is added to division time so that the division time is extended, which is disadvantage of the prior art. Further, if the dividend is negative, a complement of 2 of a reminder also must be taken to be corrected, thereby further increasing the division time.